#include <stdlib.h>
#include <stdio.h>

#include "general.h"

#include "dlx.h"
#include "sudoku.h"
#include "solver.h"

#define getCandidate(i) ((i)%(GRID_SIZE)+1)
#define getColumn(i)    (((i)%(GRID_SIZE*GRID_SIZE))/GRID_SIZE)
#define getRow(i)       ((i)/(GRID_SIZE*GRID_SIZE))
#define getRegion(i)    ((getRow(i)/SUB_GRID_SIZE)*(GRID_SIZE/SUB_GRID_SIZE)+(getColumn(i)/SUB_GRID_SIZE))
#define linkCellsLR(l, r) ((l)->R)=(r);((r)->L)=(l);
#define linkCellsUD(u, d) ((u)->D)=(d);((d)->U)=(u);

/* cover node c */
inline void coverNode(Node c) 
{
  (c->D)->U = c->U;
  (c->U)->D = c->D;
  (c->C)->size = (c->C)->size - 1;
}

/* uncover node c */
inline void uncoverNode(Node c) 
{
  (c->C)->size = (c->C)->size + 1;
  (c->D)->U = c;
  (c->U)->D = c;
}

/* cover an entire row from sparse matrix */
void coverRow(Node n)
{
  Node cur;
  for (cur = n->R; cur != n; cur = cur->R)
    {
      coverNode(cur);
    }
}

/* uncover an entire row from sparse matrix */
void uncoverRow(Node n)
{
  Node cur;
  for (cur = n->L; cur != n; cur = cur->L)
    {
      uncoverNode(cur);
    }
}

/* cover a column */
void coverColumn(Node c)
{
  Node cur;
  
  (c->R)->L = c->L;
  (c->L)->R = c->R;

  for (cur = c->D; cur != c; cur = cur->D)
    {
      coverRow(cur);
    }
}

/* uncover a column */
void uncoverColumn(Node c)
{
  Node cur;
  
  for (cur = c->U; cur != c; cur = cur->U)
    {
      uncoverRow(cur);
    }
  
  (c->R)->L = c;
  (c->L)->R = c;
}

/* remove an entire row from sparse matrix */
void removeRow(SparseMatrix sm, int row)
{
  Node cur = sm->rowHead[row];

  do
    {
      coverNode(cur);
      cur = cur->R;
    }
  while (cur != sm->rowHead[row]);
  sm->rowHead[row] = NULL;
}

/* translated candidate to sparse matrix row index */
inline int candidateToRow (int candidate, int column, int row)
{
  return row*GRID_SIZE*GRID_SIZE + column*GRID_SIZE + candidate-1;
}

/* append node N to columnHead c */
void appendColumn (Node c, Node n)
{
  Node cur;
  n->column = c->column;
  n->C = c;
  for (cur = c; cur->D != c; cur = cur->D);
  n->U = cur;
  n->D = (cur->D);
  (cur->D)->U = n;
  cur->D = n;
}

/* create and initialize new sparse matrix */
SparseMatrix newSparseMatrix(void)
{
  int i;
  int cell, row, column, region, candidate;
  SparseMatrix new = malloc(sizeof(SparseMatrix_T));
  if (new == NULL)
    {
      fprintf(stderr, "ERROR: `newSparseMatrix()' memory allocation failed!\n");
      exit(1);
    }

  /* set root */
  linkCellsLR(&(new->root), &(new->columnHead[0]));

  /* initialize and link column heads*/
  smIterateColumns(i)
    {
      new->columnHead[i].column = i;
      new->columnHead[i].size = GRID_SIZE;
      new->columnHead[i].U = &(new->columnHead[i]);
      new->columnHead[i].D = &(new->columnHead[i]);

      if (i < 4*GRID_SIZE*GRID_SIZE-1)
	{
	  linkCellsLR(&(new->columnHead[i]), &(new->columnHead[i+1]));
	}
      else
	{
	  linkCellsLR(&(new->columnHead[i]), &(new->root));
	}
    }

  /* initialize and link rows */
  smIterateRows(i)
    {
      /* set row pointer */
      new->rowHead[i] = &(new->cells[4*i]);

      /* link rows */
      linkCellsLR(&(new->cells[4*i  ]), &(new->cells[4*i+1]));
      linkCellsLR(&(new->cells[4*i+1]), &(new->cells[4*i+2]));
      linkCellsLR(&(new->cells[4*i+2]), &(new->cells[4*i+3]));
      linkCellsLR(&(new->cells[4*i+3]), &(new->cells[4*i  ]));

      /* get row id */
      new->cells[4*i  ].row = i;
      new->cells[4*i+1].row = i;
      new->cells[4*i+2].row = i;
      new->cells[4*i+3].row = i;

      row = getRow(i);
      column = getColumn(i);
      region = getRegion(i);
      cell = row*GRID_SIZE + column;
      candidate = getCandidate(i);

      /* cell constraint */
      appendColumn(&(new->columnHead[cell]), &(new->cells[4*i]));

      /* row constraint */
      appendColumn(&(new->columnHead[row*GRID_SIZE+candidate-1    +   GRID_SIZE*GRID_SIZE]), 
		   &(new->cells[4*i+1]));

      /* column constraint */
      appendColumn(&(new->columnHead[column*GRID_SIZE+candidate-1 + 2*GRID_SIZE*GRID_SIZE]), 
		   &(new->cells[4*i+2]));

      /* region constraint */
      appendColumn(&(new->columnHead[region*GRID_SIZE+candidate-1 + 3*GRID_SIZE*GRID_SIZE]), 
		   &(new->cells[4*i+3]));
    }
  
  return new;
}

void delSparseMatrix(SparseMatrix sm)
{
  free(sm);
}

void prtSparseMatrixRow(Node n)
{
  Node cur;
  int i, last_c;
  
  for (i = 0; i < n->column; i++)
    {
      printf("  |");
    }
  //printf("* |");
  printf("%.2x|", n->column);
  last_c = n->column;
  for (cur = n->R; cur != n; cur = cur->R)
    {
      for (i = 0; i < cur->column - last_c - 1; i++)
	{
	  printf("  |");
	}
      //printf("* |");
      printf("%.2x|", cur->column);
      last_c = cur->column;
    }
  for (i = 0; i < 4*GRID_SIZE*GRID_SIZE - last_c - 1; i++)
    {
      printf("  |");
    }
}

void prtSparseMatrix(SparseMatrix sm)
{
  int i, j;

  printf("(c,r,c,r)\t|");
  smIterateColumns(i)
  {
    printf("%.2x ", i);
  }
  printf("\n");
  printf("         \t|");
  smIterateColumns(i)
  {
    printf("%.2x ", sm->columnHead[i].size);
  }
  printf("\n");
  smIterateRows(i)
  {
    printf("(%d,%d,%d,%d)\t|", getCandidate(i), getRow(i), getColumn(i), getRegion(i));
    if (sm->rowHead[i] == NULL)
      {
	smIterateColumns(j)
	{
	  printf("  |");
	}
      }
    else
      {
	prtSparseMatrixRow(sm->rowHead[i]);
      }
    printf("\n");
  }
}

void prtSearchSolution(Node O[])
{
  int i;
  Grid grid;
  grid = newGrid();

  for (i = 0; i < GRID_SIZE*GRID_SIZE; i++)
    {
      setCell(getCandidate(O[i]->row), &(gridIndex(grid, getColumn(O[i]->row), getRow(O[i]->row))));
    }
  printf("solution:\n");
  prtGrid(grid, 1);
}

/* choose a column to perform cover */
Node chooseColumn(Node root)
{
  int s = GRID_SIZE + 1;
  Node cur = root->R;
  Node c = cur;

  for (cur = root->R; cur != root; cur = cur->R)
    {
      if (cur->size < s)
	{
	  c = cur;
	  s = cur->size;
	}
    }

  return c;
}

bool search(SparseMatrix sm, Node O[], int k)
{
  Node c;
  Node r;
  Node j;

  if (sm->root.R == &(sm->root)) 
    {
      prtSearchSolution(O);
      return TRUE;		/* we're done */
    }
  c = chooseColumn(&(sm->root));
  coverColumn(c);
  for (r = c->D; r != c; r = r->D)
    {
      O[k] = r;
      for (j = r->R; j != r; j = j->R)
	{
	  coverColumn(j->C);
	}
      search(sm, O, k+1);
      r = O[k];
      c = r->C;
      for (j = r->L; j != r; j = j->L)
	{
	  uncoverColumn(j->C);
	}
    }
  uncoverColumn(c);
  return TRUE;
}

bool dlx(SparseMatrix sm)
{
  Node O[GRID_SIZE*GRID_SIZE];
  return search(sm, O, 0);
}
